One of the elements within a computer operating system is memory management. Memory management consists of harware and software that controls the allocation and use of physical memory. The effect of memory management is exemplified in multiprograming systems in which several processes reside in memory at the same time. Memory management typically includes a virtual memory system. The virtual memory system provides the CPR (Central processing unit) with mapping information. The CPU generates virtual addresses when an image is executed. Before these virtual addresses can be used in access instructions and data, they must be translated into physical addresses. Memory management software maintains tables of mapping information (page tables) that keep track of where each page of virtual addresses is located in physical memory. The CPU uses this mapping information when it translates virtual addresses to physical addresses. The mapping of virtual addresses through page tables in a virtual memory system provides a large virtual address space, and allows programs to run on hardware with smaller physical memory configurations.
The range of virtual addresses is referred to as the virtual address space. The virtual address space is that set of virtual addresses accessible by the current process. A process is current when its process context is loaded into the CPU and the process is actively executing. Only one process may be current on a given CPU at a given time. In existing systems, the virtual address space is divided into a shared address space, sometimes referred to as the system address space, and a per-process address space. The perprocess address space is referred to as process private space. The shared address space maps code and data shared by all processes, and that is available to any process that is current. The shared address space may for example contain operating system code and data used by all processes. The process private space maps code and data associated with and available to one specific process only when that specific process is current. When the process context is changed, a new process is made current, and the mapping of process private space is changed to map process private space to process private code and data of that process.
A page table is typically used to map the virtual address space to physical memory, in units of "pages". A page is a multibyte unit of memory having a predetermined size. The specific size of a page varies from system to system. A page table contains page table entries (PTEs), each one of which defines a relationship (referred to as a "mapping") between a single virtual page and a physical page of memory. The physical address of a physical page of memory is referred to as a page frame number (PFN). Thus a given virtual page of memory is "mapped" to a page of physical memory by a specific PTE, and similarly that physical page of memory is "mapped" to the virtual page by that specific PTE. The PTE in that case is referred to as "mapping" the virtual page and the physical page of memory.
In existing computer systems, page table entries within a page table may be located in either process private or shared space. Where page table entries mapping process private space for a given process are located within process private space, the contents of those page table entries can ordinarily only be accessed when that specific process is current. Thus for a process to access the process private page table entries of another process, a context switch is typically required.
As computer systems evolve, the size of the virtual addresses they support grows. For example, some newer generations of computer systems use 64 bit virtual addresses, in contrast with past generations in which smaller sizes were used. The amount of virtual address space that may be addressed by a process on such newer systems is potentially as large as is permitted by the larger virtual address size. However, implementing the full range of virtual space permitted by such larger virtual address sizes may be prohibitively costly in terms of hardware bits in a virtual to physical address translation cache, the size of page tables required to map the entire space, or the complexity of accessing page table entries within such large page tables.
As a result, it is desirable to implement only a subset of the full range of virtual space permitted by large virtual address sizes. Implementation of a subset of the full range of virtual space would result in one or more "gaps" within the virtual address space. Such resulting gaps would be areas of the virtual address space for which no page table entries could be obtained to map physical memory. Accordingly virtual addresses within such gaps could not be accessed by a process that is currently executing. In a typical existing process, attempts by an existing process to access a virtual address within any inaccessible gap in the virtual address space result in an execution error.
In existing systems, when a process is initially created, some minimal set of virtual addresses is allocated to that process in order that the process may execute. When the process executes, it issues requests to the operating system for allocation and/or deallocation of further virtual addresses according to its resource needs. The allocation of virtual addresses by the operating system typically involves addition of page table entries to the page table structure. These newly added page table entries are subsequently used to map the newly allocated virtual addresses to physical memory. When a deallocation request is subsequently received to deallocate those virtual addresses, the operating system removes the page table entries from the page table.
In existing systems the executing process is permitted to allocate virtual addresses only within a predetermined virtually contiguous range of virtual addresses. No accommodation is made for any gaps in the virtual address space, and consequently inaccessible gaps in the virtual address space cannot exist within the range of virtual addresses that may be allocated to the executing process. As a result, the range of virtual addresses that may be allocated by an executing process must be fully implemented by the operating system. As the range of virtual addresses that may be allocated by an executing process is advantageously a very large portion of the total virtual address space, the lack of gap accomodation in existing systems imposes a significant limitation with regard to flexibility. Moreover, as computer systems continue to develop, the amount of virtual address space needed for process execution will increase, thus exacerbating the problem.
For these reasons and others there is required a new memory management and virtual addressing system in which the entire virtual address space need not be implemented. In the new system the currently executing process must be allocated virtual addresses in spite of any gaps of inaccessible virtual addresses located anywhere in the virtual address space of the system. The new system should specifically permit one or more gaps to be present within the range of virtual addresses which may be allocated to the executing process. And the new system should be easily extensible to future implementations in which any gaps of inaccessible virtual addresses are decreased or eliminated.